/**
 * 给定数组，求最长子序列满足和等于Target
 * 
 * 只需要将代价看作是值，收益看作是数量即可
 * 标准的01背包 
 * 
 */
using vi = vector<int>;
using vvi = vector<vi>;

int N;
vi D;

int chkadd(int a, int b){
    if(-1 != a and -1 != b) return a + b;
    return -1;
}

void chkmax(int & d, int a){
    if(-1 == a) return;
    if(-1 == d or d < a) d = a;
}

class Solution {
public:
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        N = nums.size();
        D.assign(target + 1, -1);
        D[0] = 0;
        for(auto i : nums)for(int v=target;v>=i;--v){
            chkmax(D[v], chkadd(D[v - i], 1));
        }    
        return D[target];    
    }
};
